package com.ywk.base.dataStructure.algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
//贪心算法
public class GreedyAlgorithm {

	public static void main(String[] args) {
		HashMap<String, HashSet<String>> broadcasts=new HashMap<>();
		
		HashSet<String> h1=new HashSet<>();
		h1.add("北京");
		h1.add("上海");
		h1.add("天津");
		h1.add("成都");
		
		HashSet<String> h2=new HashSet<>();
		h2.add("大连");
		h2.add("天津");
		
		HashSet<String> h3=new HashSet<>();
		h3.add("上海");
		h3.add("杭州");
		
		HashSet<String> h4=new HashSet<>();
		h4.add("天津");
		h4.add("上海");
		
		HashSet<String> h5=new HashSet<>();
		h5.add("北京");
		h5.add("广州");
		h5.add("深圳");
		h5.add("成都");
		
		broadcasts.put("k1", h1);
		broadcasts.put("k2", h2);
		broadcasts.put("k3", h3);
		broadcasts.put("k4", h4);
		broadcasts.put("k5", h5);
		
		HashSet<String> allAreas = new HashSet<>();
		allAreas.add("北京");
		allAreas.add("上海");
		allAreas.add("天津");
		allAreas.add("广州");
		allAreas.add("深圳");
		allAreas.add("成都");
		allAreas.add("杭州");
		allAreas.add("大连");
		
		ArrayList<String> selects = new ArrayList<>(); 
		String maxkey=null;//通过比较找出覆盖最多地区的广播电台
		while(allAreas.size()>0) {
			HashSet<String> temp=new HashSet<String>();//当前键对应的值
			HashSet<String> reserve = new HashSet<String>();//保存上一次遍历的键对应的值
			for(String key:broadcasts.keySet()) {//通过键来遍历对应的值
				temp.addAll(broadcasts.get(key));
				temp.retainAll(allAreas);
				if(temp.size()>0&&(maxkey==null||temp.size()>reserve.size())) {
					maxkey=key;
					reserve.addAll(broadcasts.get(maxkey));
					//求出reserve与allAreas的交集并赋给reserve
					reserve.retainAll(allAreas);
				}
				temp.clear();
			}
			if(maxkey!=null) {
				selects.add(maxkey);
				allAreas.removeAll(broadcasts.get(maxkey));
			}
			maxkey=null;
		}
		System.out.println("结果："+selects);
	}

}
